\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url,charter}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Feng Shi}{}{#3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}

\handout{1}{2013.7.10}{Problem Set 4}

\paragraph{Problem 1} (No collaborater.)
For any small constant $\epsilon$, find an $\epsilon$-Nash equilibrium that is not a Nash 
equilibrium, in the 6-player star-shape matching pennies game introduced in class.

\textbf{Solution:}

There is a unique Nash equilibrium $\sigma_i=\frac{1}{2}H+\frac{1}{2}T$ for $i\in[1,6]$. 
This can be seen by calculating player $i$'s expected utility from the $2$ players adjacent
to him. (same as the $2-$player matching pennies)\\
$\sigma'_i=(\frac{1}{2}+\frac{\epsilon}{4})H+(\frac{1}{2}-\frac{\epsilon}{4})T$ is a $\epsilon-$
Nash equilibrium but is not a Nash equilibrium for $\epsilon\in(0,1)$.\\
We denote by $u_i(s_l,\sigma_i,s_r)$ the utility of player $i$ with his lefthand neighbour playing
strategy $s_l$ and his righthand neighbour playing $s_r$. Then
\begin{align*}
	&u_i(\sigma)=2(
	(\frac{1}{2}+\frac{\epsilon}{4})^2+(\frac{1}{2}-\frac{\epsilon}{4})^2
	-(\frac{1}{2}+\frac{\epsilon}{4})(\frac{1}{2}-\frac{\epsilon}{4})
	-(\frac{1}{2}-\frac{\epsilon}{4})(\frac{1}{2}+\frac{\epsilon}{4})
	)=\frac{\epsilon^2}{2}< \frac{\epsilon^2}{2}+\epsilon\\
	&u_i(H,\sigma_i,H)=2((\frac{1}{2}+\frac{\epsilon}{4})-(\frac{1}{2}-\frac{\epsilon}{4}))
		=\epsilon<\frac{\epsilon^2}{2}+\epsilon\\
	&u_i(H,\sigma_i,T)=u_i(T,\sigma_i,H)=
		(\frac{1}{2}+\frac{\epsilon}{4})-(\frac{1}{2}+\frac{\epsilon}{4})
		=(\frac{1}{2}-\frac{\epsilon}{4})-(\frac{1}{2}-\frac{\epsilon}{4})
		=0<\frac{\epsilon^2}{2}+\epsilon\\
	&u_i(T,\sigma_i,T)=2((\frac{1}{2}-\frac{\epsilon}{4})-(\frac{1}{2}+\frac{\epsilon}{4}))
		=-\epsilon<\frac{\epsilon^2}{2}+\epsilon
\end{align*}
So $\sigma'_i=(\frac{1}{2}+\frac{\epsilon}{4})H+(\frac{1}{2}-\frac{\epsilon}{4})T$ is a $\epsilon-$
Nash equilibrium but is not a Nash equilibrium for $\epsilon\in(0,1)$.\\


\bigskip

\paragraph{Problem 2} (No collaborater.)
Work out the algorithm TreeNash for the same game in Problem 1. 
That is, write out (or give compact description) of all the tables and witness lists generated by
the algorithm. Then describe all the NEs of this game, following the top-down procedure.

\textbf{Solution:}

\bigskip

\paragraph{Problem 3} (No collaborator.)
Prove that for any finite game $G$, any finite convex combination of CEs is still a CE of $G$.
(If $\sigma^1, \dots, \sigma^k\in \Delta(S)$, and if $\lambda_1, \dots, \lambda_k$ are non-negative 
reals with $\sum_i \lambda_i = 1$, then the convex combination of $\sigma^1,\dots, \sigma^k$ under
$\lambda_1, \dots, \lambda_k$ is the distribution $\lambda_1 \sigma^1 + \cdots + \lambda_k \sigma^k$.)

\textbf{Solution:}

Let $u^1,u^2,...,u^k$ be the utility profiles of $k$ correlated Nash equilibria 
$\langle (\Omega^j,\pi^j),(P_{i}^j),(\sigma_{i}^j)\rangle$ $(j=1,2,...,k)$.
For any non-negative reals $\lambda^1,\lambda^2,...,\lambda^k$
where $\displaystyle \sum_{i=1}^{k}=\lambda^i=1$, we prove that following yields a correlated 
equilibrium:
\begin{quote}
	$\langle (\Omega,\pi),(P_i),(\sigma_i)\rangle$ where \\
	$\Omega=\cup_{i}\Omega ^i,\\
	\forall w\in\Omega^i\subset\Omega, \ \pi(w)=\lambda^i\pi^i(w)\\
	P_i=\cup_{j}P_{i}^j\\
	\forall w\in\Omega^j, \ \sigma_i(w)=\sigma_{i}^j(w)$
\end{quote}
And its utility is $\displaystyle u'=\sum_{i=1}^k \lambda^i u^i$. \\
By convex combination we have $$\forall i\in N, \  
\displaystyle \forall w\in \Omega, \ u'_i\geq \min_{\substack{j\in[1,k]}} u_{i}^j\geq 
\max_{\substack{j\in[1,k]}} u_{i}^j(\sigma_{-i}(w),\tau_i(w))$$
So it is a correlated Nash equilibrium.

\bibliographystyle{agsm}

\begin{thebibliography}{99}

\bibitem{OR94}{M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.}

\bibitem{NRTV07}{N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds).
	\\{\em Algorithmic game theory.} Cambridge University Press, 2007. }

\end{thebibliography}

\end{document}
